Interactive advertising on the Internet relies upon providing relevant messages to users. In advertising systems that provide relevant sponsored messages accompanying search results, such as Google AdWords, a user search query seeking search results can also be used to target advertisements to accompany those search results. Such a system is described, for example, in U.S. Pat. No. 6,816,857, entitled “Meaning-Based Advertising and Document Relevance Determination,” issued Nov. 9, 2004, and incorporated by reference in its entirety herein.